package cn.edu.cdu.argorithm.impl;

import cn.edu.cdu.argorithm.ILargestRectangleInHistogram;

import java.util.ArrayDeque;
import java.util.Deque;

public class LargestRectangleInHistogramSolutions {
    public static class Solution1 implements ILargestRectangleInHistogram{
        @Override
        public int largestRectangleArea(int[] heights) {
            int n = heights.length;
            if (n == 0) {
                return 0;
            }
            if(n == 1) {
                return heights[0];
            }
            int area = Integer.MIN_VALUE;
            Deque<Integer> stack = new ArrayDeque<>();
            for (int i = 0; i < n; i++) {
                while (!stack.isEmpty() && heights[stack.peekLast()] > heights[i]) {
                    int height = heights[stack.removeLast()];
                    while(!stack.isEmpty() && heights[stack.peekLast()] == height) {
                        stack.removeLast();
                    }
                    int width;
                    if (stack.isEmpty()) {
                        width = i;
                    } else {
                        width = i - stack.peekLast() - 1;
                    }
                    area = Math.max(area, height * width);
                }
                stack.addLast(i);
            }
            while (!stack.isEmpty()) {
                int height = heights[stack.removeLast()];
                while(!stack.isEmpty() && heights[stack.peekLast()] == height) {
                    stack.removeLast();
                }
                int width;
                if (stack.isEmpty()) {
                    width = n;
                } else {
                    width = n - stack.peekLast() - 1;
                }
                area = Math.max(area, height * width);
            }
            return area;
        }

        public static class Solution2 implements ILargestRectangleInHistogram{
            @Override
            public int largestRectangleArea(int[] heights) {
                int n = heights.length;
                if (n == 0) {
                    return 0;
                }
                if(n == 1) {
                    return heights[0];
                }
                int area = Integer.MIN_VALUE;
                int[] newHeights = new int[n + 2];
                System.arraycopy(heights, 0, newHeights, 1, n);
                heights = newHeights;
                n += 2;
                Deque<Integer> stack = new ArrayDeque<>();
                stack.addLast(0);
                for (int i = 0; i < n; i++) {
                    while (!stack.isEmpty() && heights[stack.peekLast()] > heights[i]) {
                        int height = heights[stack.removeLast()];
                        int width = i - stack.peekLast() - 1;
                        area = Math.max(area, height * width);
                    }
                    stack.addLast(i);
                }
                System.out.println(stack.size());
                return area;
            }
        }
    }
}
